{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Height by Stacking Cuboids "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxHeight"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #堆叠长方体的最大高度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你 <code>n</code> 个长方体 <code>cuboids</code> ，其中第 <code>i</code> 个长方体的长宽高表示为 <code>cuboids[i] = [width<sub>i</sub>, length<sub>i</sub>, height<sub>i</sub>]</code>（<strong>下标从 0 开始</strong>）。请你从 <code>cuboids</code> 选出一个 <strong>子集</strong> ，并将它们堆叠起来。</p>\n",
    "\n",
    "<p>如果 <code>width<sub>i</sub> <= width<sub>j</sub></code> 且 <code>length<sub>i</sub> <= length<sub>j</sub></code> 且 <code>height<sub>i</sub> <= height<sub>j</sub></code> ，你就可以将长方体 <code>i</code> 堆叠在长方体 <code>j</code> 上。你可以通过旋转把长方体的长宽高重新排列，以将它放在另一个长方体上。</p>\n",
    "\n",
    "<p>返回 <strong>堆叠长方体</strong> <code>cuboids</code> 可以得到的 <strong>最大高度</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/12/12/image.jpg\" style=\"width: 420px; height: 299px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cuboids = [[50,45,20],[95,37,53],[45,23,12]]\n",
    "<strong>输出：</strong>190\n",
    "<strong>解释：</strong>\n",
    "第 1 个长方体放在底部，53x37 的一面朝下，高度为 95 。\n",
    "第 0 个长方体放在中间，45x20 的一面朝下，高度为 50 。\n",
    "第 2 个长方体放在上面，23x12 的一面朝下，高度为 45 。\n",
    "总高度是 95 + 50 + 45 = 190 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cuboids = [[38,25,45],[76,35,3]]\n",
    "<strong>输出：</strong>76\n",
    "<strong>解释：</strong>\n",
    "无法将任何长方体放在另一个上面。\n",
    "选择第 1 个长方体然后旋转它，使 35x3 的一面朝下，其高度为 76 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cuboids = [[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]\n",
    "<strong>输出：</strong>102\n",
    "<strong>解释：</strong>\n",
    "重新排列长方体后，可以看到所有长方体的尺寸都相同。\n",
    "你可以把 11x7 的一面朝下，这样它们的高度就是 17 。\n",
    "堆叠长方体的最大高度为 6 * 17 = 102 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == cuboids.length</code></li>\n",
    "\t<li><code>1 <= n <= 100</code></li>\n",
    "\t<li><code>1 <= width<sub>i</sub>, length<sub>i</sub>, height<sub>i</sub> <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-height-by-stacking-cuboids](https://leetcode.cn/problems/maximum-height-by-stacking-cuboids/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-height-by-stacking-cuboids](https://leetcode.cn/problems/maximum-height-by-stacking-cuboids/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[50,45,20],[95,37,53],[45,23,12]]', '[[38,25,45],[76,35,3]]', '[[7,11,17],[7,17,11],[11,7,17],[11,17,7],[17,7,11],[17,11,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        n = len(cuboids)\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        dp = [0]*n\n",
    "        dp[0] = cuboids[0][2]\n",
    "        ans = 0\n",
    "        for i in range(0,n):\n",
    "            dp[i] = cuboids[i][2]\n",
    "            for j in range(i):\n",
    "                if cuboids[i][1]>=cuboids[j][1] and cuboids[i][2]>=cuboids[j][2]:\n",
    "                    dp[i] = max(dp[i], dp[j]+cuboids[i][2])\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# ref: https://leetcode.cn/problems/maximum-height-by-stacking-cuboids/solutions/2014514/tu-jie-suan-fa-you-hua-xiang-xi-zheng-mi-b6fq/\n",
    "# 为什么可以直接加最长边？ - 因为堆的时候就是“长对长，中对中，短对短”\n",
    "# O(n**2), O(n)\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        n = len(cuboids)\n",
    "        if n == 1:\n",
    "            return max(cuboids[0])\n",
    "\n",
    "        dp = [0] * n\n",
    "\n",
    "        for c in cuboids:\n",
    "            c.sort(reverse = True)  \n",
    "        cuboids = sorted(cuboids,key = lambda x: (x[0],x[1],x[2]),reverse = True)\n",
    "\n",
    "        for i,(w1,l1,h1) in enumerate(cuboids):\n",
    "            for j,(w2,l2,h2) in enumerate(cuboids[:i]):\n",
    "                if w2 >= w1 and l2 >= l1 and h2 >= h1:\n",
    "                    dp[i] = max(dp[i],dp[j])\n",
    "            dp[i] += w1\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        # 长方体递减堆叠的最大高度：长宽高都递减\n",
    "\n",
    "        n = len(cuboids)\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort(key = sum)\n",
    "        ans = 0\n",
    "        dp = [0] * n # cuboids[0...i]堆叠后的最大高度\n",
    "        for i in range(n):\n",
    "            dp[i] = cuboids[i][2]\n",
    "            for j in range(i):\n",
    "                if cuboids[i][0] >= cuboids[j][0] and cuboids[i][1] >= cuboids[j][1] \\\n",
    "                    and cuboids[i][2] >= cuboids[j][2]: \n",
    "                    dp[i] = max(dp[i], dp[j] + cuboids[i][2])\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for v in cuboids:\n",
    "            v.sort()\n",
    "        cuboids.sort()\n",
    "        n = len(cuboids)\n",
    "        tree = [[0]*101 for _ in range(101)]\n",
    "        def upd(i,j,v):\n",
    "            while i <= 100:\n",
    "                j1 = j\n",
    "                while j1 <= 100:\n",
    "                    tree[i][j1] = max(tree[i][j1],v)\n",
    "                    j1 += j1&-j1\n",
    "                i += i&-i \n",
    "        def get(i,j):\n",
    "            s = 0 \n",
    "            while i:\n",
    "                j1 = j\n",
    "                while j1:\n",
    "                    s = max(s, tree[i][j1])\n",
    "                    j1 -= j1&-j1 \n",
    "                i -= i&-i \n",
    "            return s        \n",
    "        \n",
    "        for _,b,c in cuboids:            \n",
    "            upd(b,c,c+get(b,c))\n",
    "            \n",
    "        return get(100,100)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        n = len(cuboids)\n",
    "        f = [0] * n\n",
    "        res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            w1, l1, h1 = cuboids[i]\n",
    "            for j in range(i):\n",
    "                w2, l2, h2 = cuboids[j]\n",
    "                if l1 >= l2 and h1 >= h2:\n",
    "                    f[i] = max(f[i], f[j])\n",
    "            f[i] += h1 \n",
    "            res = max(res, f[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        # 首先按宽度、长度和高度进行排序\n",
    "        for cuboid in cuboids:\n",
    "            cuboid.sort()\n",
    "        \n",
    "        cuboids.sort()\n",
    "        \n",
    "        # dp[i] 表示以第 i 个长方体为顶部能达到的最大高度\n",
    "        dp = [0] * len(cuboids)\n",
    "        \n",
    "        for i in range(len(cuboids)):\n",
    "            dp[i] = cuboids[i][2]\n",
    "        \n",
    "        for i in range(1, len(cuboids)):\n",
    "            for j in range(i):\n",
    "                # 如果长方体 i 可以放在长方体 j 上面\n",
    "                if cuboids[i][0] >= cuboids[j][0] and cuboids[i][1] >= cuboids[j][1] and cuboids[i][2] >= cuboids[j][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + cuboids[i][2])\n",
    "        \n",
    "        return max(dp)\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.maxHeight([[50,45,20],[95,37,53],[45,23,12]]))  # 输出应为 190\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, c: List[List[int]]) -> int:\n",
    "        def f(x):\n",
    "            i, j, k = x \n",
    "            return set([(i, j, k), (i, k, j), (k, i, j), (k, j, i), (j, i, k), (j, k, i)])\n",
    "        s = []\n",
    "        for j in c:\n",
    "            for k in f(j):\n",
    "                s.append(k) \n",
    "        s.sort()\n",
    "        n = len(s)\n",
    "        ans = {0:s[0][-1]} \n",
    "        for j in range(1, n):\n",
    "            tmp = 0 \n",
    "            for k in range(j):\n",
    "                \n",
    "                if s[k][0]<=s[j][0]:\n",
    "                    if s[k][1]<=s[j][1]:\n",
    "                        if s[k][2]<=s[j][2]:\n",
    "                            tmp = max(tmp, ans[k])\n",
    "            ans[j] = tmp + s[j][-1]\n",
    "        return max(ans.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        f = [[0] * 6 for _ in range(len(cuboids))]\n",
    "        for i, c2 in enumerate(cuboids):\n",
    "            for j, (w2, l2, h2) in enumerate(permutations(c2)):\n",
    "                for k, c1 in enumerate(cuboids[:i]):\n",
    "                    for l, (w1, l1, h1) in enumerate(permutations(c1)):\n",
    "                        if w1 <= w2 and l1 <= l2 and h1 <= h2:\n",
    "                            f[i][j] = max(f[i][j], f[k][l])\n",
    "                f[i][j] += h2\n",
    "        return max(max(d) for d in f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for v in cuboids:\n",
    "            v.sort()\n",
    "        cuboids.sort()\n",
    "        n = len(cuboids)\n",
    "        f = [0]*n\n",
    "        for i,(_,b,c) in enumerate(cuboids):\n",
    "            f[i] = max([f[j] for j in range(i) if cuboids[j][1] <= b and cuboids[j][2] <= c],default=0) + c \n",
    "        return max(f)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        n = len(cuboids)\n",
    "        for i in range(n):\n",
    "            cuboids[i].sort()\n",
    "        cuboids.sort()\n",
    "        dp = [0] * n\n",
    "        dp[0] = cuboids[0][2]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = cuboids[i][2]\n",
    "            for j in range(i): \n",
    "                if cuboids[i][1] >= cuboids[j][1] and cuboids[i][2] >= cuboids[j][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + cuboids[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        A = cuboids\n",
    "        n = len(A)\n",
    "        for a in A:\n",
    "            a.sort(reverse = True)\n",
    "        A.sort(reverse = True)\n",
    "\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            dp[i] = A[i][0]\n",
    "            for j in range(i):\n",
    "                if A[j][1] >= A[i][1] and A[j][2] >= A[i][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + A[i][0])\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        n = len(cuboids)\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        dp = [0]*n\n",
    "        ans = 0\n",
    "        for i in range(0,n):\n",
    "            dp[i] = cuboids[i][2]\n",
    "            for j in range(i):\n",
    "                if cuboids[i][1]>=cuboids[j][1] and cuboids[i][2]>=cuboids[j][2]:\n",
    "                    dp[i] = max(dp[i], dp[j]+cuboids[i][2])\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        dp = [0] * len(cuboids)\n",
    "        for i in range(len(cuboids)):\n",
    "            wi, li, hi = cuboids[i]\n",
    "            for j in range(0, i):\n",
    "                wj, lj, hj = cuboids[j]\n",
    "                if wj <= wi and lj <= li and hj <= hi:\n",
    "                    dp[i] = max(dp[i], dp[j])\n",
    "            dp[i] += hi\n",
    "        return max(dp)                                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        n = len(cuboids)\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        dp = [0]*n\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if cuboids[i][1]>=cuboids[j][1] and cuboids[i][2]>=cuboids[j][2]:\n",
    "                    dp[i] = max(dp[i], dp[j])\n",
    "            dp[i] += cuboids[i][2]\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    ** 理解的不够！！！ **\n",
    "    线性DP\n",
    "    假设某个长方体上可以放三个满足题目要求的长方体，那么将这三个长方体“同时”旋转，每一个长方体都已\n",
    "    长宽高中最长的作为高，这三个长方体依然满足堆叠的要求，且此时整体堆叠的高度最高\n",
    "    此时会产生两个问题：\n",
    "    1.为什么满足要求的两个长方体同时旋转后依然能满足堆放要求？\n",
    "    假设原始满足要求的两个长方体，对应长宽高的形态为\n",
    "    w1 <= l1 <= h1    第一个长方形\n",
    "    ^     ^     ^\n",
    "    w2 <= l2 <= h2    第二个长方形\n",
    "    第一个长方形的最小值一定 小于 第二个长方形的最小值，因为假设第一个长方形的最小值大于第二个长方形的最小值，\n",
    "    那么第一个长方形中的另外两条边肯定也大于第二个长方形中的最小值，这种肯定就没法嵌套了\n",
    "    同理第一个长方形的最大值一定 小于 第二个长方形的最大值\n",
    "    上面两个结论，无论怎么排序都是满足的，否则肯定无法嵌套，现在就看按照从小到大的顺序排列后，是否有l1 <= l2。\n",
    "    假设排序后不满足，即满足l1 > l2，如果这样的话，对于l1来说只能和h2对应，而h1 >= l1，所以h1也只能和h2对应，\n",
    "    w1则对应w2和l2两个，这个不可能出现，也就不能堆叠，和一开始两个长方形可以堆叠矛盾\n",
    "    2.为什么以高度最为最大值摆放就能让整体堆放的高度最高？\n",
    "    因为比长方形a小的满足要求的长方形有3个，将a最长的边作为高度，此时比它小的3个也会同时旋转，其他任何一个不满足要求\n",
    "    的也不会通过旋转变成满足要求\n",
    "    '''\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        n = len(cuboids)\n",
    "        for i in range(n):\n",
    "            cuboids[i].sort()\n",
    "        cuboids.sort()\n",
    "        dp = [0] * n\n",
    "        dp[0] = cuboids[0][2]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = cuboids[i][2]\n",
    "            for j in range(i): \n",
    "                '''\n",
    "                此时只能保证最短的边长是从小到大的，其他两个边也需要满足要求\n",
    "                '''\n",
    "                if cuboids[i][1] >= cuboids[j][1] and cuboids[i][2] >= cuboids[j][2]:\n",
    "                    dp[i] = max(dp[i], dp[j] + cuboids[i][2])\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        n=len(cuboids)\n",
    "        f=[0]*n\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                if cuboids[j][1]<=cuboids[i][1] and cuboids[j][2]<=cuboids[i][2]:\n",
    "                    f[i]=max(f[i], f[j])\n",
    "            f[i]+=cuboids[i][2]\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for c in cuboids: # 长方体长宽高排序\n",
    "            c.sort()\n",
    "\n",
    "        cuboids.sort()  # 长方体个体排序\n",
    "        f = [0] * len(cuboids)\n",
    "        for i, (_, l2, h2) in enumerate(cuboids): # 遍历长方体数组\n",
    "            for j, (_, l1, h1) in enumerate(cuboids[:i]):\n",
    "                if l1 <= l2 and h1 <= h2:\n",
    "                    f[i] = max(f[i], f[j])  # 状态转移\n",
    "            f[i] += h2\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        n = len(cuboids)\n",
    "        f = [0] * (n + 1)\n",
    "\n",
    "        for i in range(n):\n",
    "            w1, l1, h1 = cuboids[i]\n",
    "            for j in range(i):\n",
    "                w2, l2, h2 = cuboids[j]\n",
    "                if l1 >= l2 and h1 >= h2:\n",
    "                    f[i] = max(f[i], f[j])\n",
    "            f[i] += h1 \n",
    "        return max(f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        f = [[0] * 6 for _ in range(len(cuboids))]\n",
    "        for i, c2 in enumerate(cuboids):\n",
    "            for j, (w2, l2, h2) in enumerate(permutations(c2)):\n",
    "                for k, c1 in enumerate(cuboids[:i]):\n",
    "                    for l, (w1, l1, h1) in enumerate(permutations(c1)):\n",
    "                        if w1 <= w2 and l1 <= l2 and h1 <= h2:\n",
    "                            f[i][j] = max(f[i][j], f[k][l])\n",
    "                f[i][j] += h2\n",
    "        return max(max(d) for d in f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for x in cuboids:\n",
    "            x.sort()\n",
    "        cuboids.sort()\n",
    "        dp = [0] * len(cuboids)\n",
    "        for i,(_,l2,h2) in enumerate(cuboids):\n",
    "            for j,(_,l1,h1) in enumerate(cuboids[:i]):\n",
    "                if l1 <= l2 and h1 <= h2:\n",
    "                    dp[i] = max(dp[i],dp[j])\n",
    "            dp[i] += h2\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        f = [0] * len(cuboids)\n",
    "        for i, (_,l2,h2) in enumerate(cuboids):\n",
    "            for j,(_,l1,h1) in enumerate(cuboids[:i]):\n",
    "                if l1<=l2 and h1<=h2:\n",
    "                    f[i] = max(f[i],f[j])\n",
    "            f[i]+=h2\n",
    "        return max(f)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        # 类似最长递增子序列的三维版本。\n",
    "        n = len(cuboids)\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        dp = [0]*n\n",
    "        ans = 0\n",
    "        for i in range(0,n):\n",
    "            dp[i] = cuboids[i][2]\n",
    "            for j in range(i):\n",
    "                if cuboids[i][1]>=cuboids[j][1] and cuboids[i][2]>=cuboids[j][2]:\n",
    "                    dp[i] = max(dp[i], dp[j]+cuboids[i][2])\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        n = len(cuboids)\n",
    "        print(cuboids)\n",
    "        f = [0] * n\n",
    "        for i, (_, l2, h2) in enumerate(cuboids):\n",
    "            for j, (_, l1, h1) in enumerate(cuboids[:i]):\n",
    "                if l1 <= l2 and h1 <= h2:\n",
    "                    f[i] = max(f[i], f[j])\n",
    "            f[i] += h2\n",
    "        return max(f)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        n = len(cuboids)\n",
    "        f = [0] * n\n",
    "        for i, (_, l2, h2) in enumerate(cuboids):\n",
    "            for j, (_, l1, h1) in enumerate(cuboids[:i]):\n",
    "                if l1 <= l2 and h1 <= h2:\n",
    "                    f[i] = max(f[i], f[j])\n",
    "            f[i] += h2\n",
    "        return max(f)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        cuboids = [sorted(ls) for ls in cuboids]\n",
    "        cuboids.sort()\n",
    "        n = len(cuboids)\n",
    "        dp = [0]*n\n",
    "        for i in range(n):\n",
    "            x,y,z = cuboids[i]\n",
    "            dp[i] = z\n",
    "            for j in range(i):\n",
    "                a,b,c = cuboids[j]\n",
    "                if a<=x and b<=y and c <= z and dp[j]+z > dp[i]:\n",
    "                    dp[i] = dp[j]+z\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "#         A = cuboids\n",
    "#         n = len(A)\n",
    "#         for a in A:\n",
    "#             a.sort(reverse = True)\n",
    "#         A.sort(reverse = True)\n",
    "#         print(A)\n",
    "#         dp = [0] * n\n",
    "#         for i in range(n):\n",
    "#             print(\"i_c: \", cuboids[i])\n",
    "#             dp[i] = A[i][0]\n",
    "#             for j in range(i):\n",
    "#                 print(\"j_c: \", cuboids[j])\n",
    "#                 if A[j][1] >= A[i][1] and A[j][2] >= A[i][2]:\n",
    "#                     dp[i] = max(dp[i], dp[j] + A[i][0])\n",
    "#             print(\"dp: \", dp)\n",
    "#         return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        n = len(cuboids)\n",
    "        if n == 1:\n",
    "            return max(cuboids[0])\n",
    "\n",
    "        dp = [0] * n\n",
    "\n",
    "        for c in cuboids:\n",
    "            c.sort(reverse = True)  \n",
    "        cuboids = sorted(cuboids,reverse = True)\n",
    "\n",
    "        for i,(w1,l1,h1) in enumerate(cuboids):\n",
    "            print(\"i_c: \", cuboids[i])\n",
    "            for j,(w2,l2,h2) in enumerate(cuboids[:i]):\n",
    "                print(\"j_c: \", cuboids[j])\n",
    "                if w2 >= w1 and l2 >= l1 and h2 >= h1:\n",
    "                    dp[i] = max(dp[i],dp[j])\n",
    "            dp[i] += w1\n",
    "            print(\"dp: \", dp)\n",
    "        return max(dp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "#         A = cuboids\n",
    "#         n = len(A)\n",
    "#         for a in A:\n",
    "#             a.sort(reverse = True)\n",
    "#         A.sort(reverse = True)\n",
    "#         print(A)\n",
    "#         dp = [0] * n\n",
    "#         for i in range(n):\n",
    "#             print(\"i_c: \", cuboids[i])\n",
    "#             dp[i] = A[i][0]\n",
    "#             for j in range(i):\n",
    "#                 print(\"j_c: \", cuboids[j])\n",
    "#                 if A[j][1] >= A[i][1] and A[j][2] >= A[i][2]:\n",
    "#                     dp[i] = max(dp[i], dp[j] + A[i][0])\n",
    "#             print(\"dp: \", dp)\n",
    "#         return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        n = len(cuboids)\n",
    "        if n == 1:\n",
    "            return max(cuboids[0])\n",
    "\n",
    "        dp = [0] * n\n",
    "\n",
    "        for c in cuboids:\n",
    "            c.sort(reverse = True)  \n",
    "        cuboids = sorted(cuboids,key = lambda x: (x[0],x[1],x[2]),reverse = True)\n",
    "\n",
    "        for i,(w1,l1,h1) in enumerate(cuboids):\n",
    "            print(\"i_c: \", cuboids[i])\n",
    "            for j,(w2,l2,h2) in enumerate(cuboids[:i]):\n",
    "                print(\"j_c: \", cuboids[j])\n",
    "                if w2 >= w1 and l2 >= l1 and h2 >= h1:\n",
    "                    dp[i] = max(dp[i],dp[j])\n",
    "            dp[i] += w1\n",
    "            print(\"dp: \", dp)\n",
    "        return max(dp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.max_tree = [0] * (n + 1)\n",
    "    def update(self, idx, val):\n",
    "        while idx <= self.n:\n",
    "            self.max_tree[idx] = max(self.max_tree[idx], val)\n",
    "            idx += idx & (-idx)\n",
    "    def query(self, idx):\n",
    "        res = 0\n",
    "        while idx > 0:\n",
    "            res = max(res, self.max_tree[idx])\n",
    "            idx -= idx & (-idx)\n",
    "        return res\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        n=len(cuboids)\n",
    "        for i in range(n):\n",
    "            cuboids[i].sort()\n",
    "        cuboids.sort(key=lambda x:(x[0],x[1],x[2]))\n",
    "        f=[z for x,y,z in cuboids]\n",
    "        pos=list(range(n))\n",
    "        pos.sort(key=lambda x:(cuboids[x][1],cuboids[x][2]))\n",
    "        #print(pos)\n",
    "        #print(cuboids)\n",
    "        def cdq(l,r,pos):\n",
    "            if l==r:\n",
    "                return \n",
    "            mid=(l+r)//2\n",
    "            left=[];right=[]\n",
    "            for i in pos:\n",
    "                if i<=mid:\n",
    "                    left.append(i)\n",
    "                else:\n",
    "                    right.append(i)\n",
    "            cdq(l,mid,left)\n",
    "            bit=BIT(105)\n",
    "            for i in pos:\n",
    "                if i<=mid:\n",
    "                    bit.update(cuboids[i][2],f[i])\n",
    "                else:\n",
    "                    f[i]=max(f[i],cuboids[i][2]+bit.query(cuboids[i][2]))\n",
    "            cdq(mid+1,r,right)\n",
    "        cdq(0,n-1,pos)\n",
    "        #print(f)\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        cuboids=[sorted(i) for i in cuboids]\n",
    "        cuboids.sort(reverse=True,key=sum)\n",
    "        n=len(cuboids)\n",
    "        dp=[0]*n\n",
    "        for i,[a,b,c] in enumerate(cuboids):\n",
    "            dp[i]=c\n",
    "            for j in range(i):\n",
    "                if cuboids[j][0]>=a and cuboids[j][1]>=b and cuboids[j][2]>=c:\n",
    "                    dp[i]=max(dp[i],dp[j]+c)\n",
    "        print(dp)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for v in cuboids:\n",
    "            v.sort()\n",
    "        cuboids.sort()\n",
    "        n = len(cuboids)\n",
    "        tree = defaultdict(lambda:defaultdict(lambda:0))\n",
    "        def upd(i,j,v):\n",
    "            while i <= 100:\n",
    "                j1 = j\n",
    "                while j1 <= 100:\n",
    "                    tree[i][j1] = max(tree[i][j1],v)\n",
    "                    j1 += j1&-j1\n",
    "                i += i&-i \n",
    "        def get(i,j):\n",
    "            s = 0 \n",
    "            while i:\n",
    "                j1 = j\n",
    "                while j1:\n",
    "                    s = max(s, tree[i][j1])\n",
    "                    j1 -= j1&-j1 \n",
    "                i -= i&-i \n",
    "            return s        \n",
    "        \n",
    "        for _,b,c in cuboids:            \n",
    "            upd(b,c,c+get(b,c))\n",
    "            \n",
    "        return get(100,100)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        # 思路： 若能堆叠起来。上面的一定：最小的和下面最小的一致\n",
    "        # 上面最大的和下面最大的一一对应\n",
    "\n",
    "        for i, x in enumerate(cuboids):\n",
    "            cuboids[i] = sorted(cuboids[i])\n",
    "\n",
    "        cuboids2 = sorted(cuboids)\n",
    "\n",
    "        n = len(cuboids)\n",
    "        dp = [0] * n\n",
    "        for i, d in enumerate(cuboids2):\n",
    "            dp[i] = d[2]\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i == 0 :\n",
    "                continue\n",
    "            for j in range(0, i):\n",
    "\n",
    "                flag = (cuboids2[i][0] >= cuboids2[j][0]) and (cuboids2[i][1] >= cuboids2[j][1]) and (cuboids2[i][2] >= cuboids2[j][2])\n",
    "\n",
    "                if flag:\n",
    "                    #  and (cuboids2[i][1] >= cuboids2[j][1]) and (cuboids2[i][2] >= cuboids2[j[2]]):\n",
    "                    dp[i] = max(dp[i], dp[j] + cuboids2[i][2])\n",
    "        print(cuboids2, dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        cuboids=[sorted(i) for i in cuboids]\n",
    "        cuboids.sort(reverse=True,key=lambda i:i[0]*i[1]*i[2])\n",
    "        n=len(cuboids)\n",
    "        dp=[0]*n\n",
    "        for i,[a,b,c] in enumerate(cuboids):\n",
    "            dp[i]=c\n",
    "            for j in range(i):\n",
    "                if cuboids[j][0]>=a and cuboids[j][1]>=b and cuboids[j][2]>=c:\n",
    "                    dp[i]=max(dp[i],dp[j]+c)\n",
    "        print(dp)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import * \n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        arr = []\n",
    "        cnt = Counter() \n",
    "        for w, l, h in cuboids:\n",
    "            tmp = sorted([w,l,h])\n",
    "            cnt[tuple(tmp)] += 1\n",
    "        for (l1,l2,l3), x in cnt.items():\n",
    "            arr.append((l1,l2,l3, x))\n",
    "        n = len(arr) \n",
    "        indegree = [0] * n \n",
    "        g = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if arr[i][0] >= arr[j][0] and arr[i][1] >= arr[j][1] and arr[i][2] >= arr[j][2]:\n",
    "                    g[i].append(j)\n",
    "                    indegree[j] += 1\n",
    "                elif arr[i][0] <= arr[j][0] and arr[i][1] <= arr[j][1] and arr[i][2] <= arr[j][2]:\n",
    "                    g[j].append(i)\n",
    "                    indegree[i] += 1\n",
    "        dp= [0] * n \n",
    "        Q = deque()\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                Q.append(i)  \n",
    "                dp[i] = arr[i][3] * arr[i][2]\n",
    "        while Q:\n",
    "            u = Q.popleft()\n",
    "            for v in g[u]:\n",
    "                dp[v] = max(dp[v], dp[u] + arr[v][3] * arr[v][2]) \n",
    "                indegree[v] -= 1\n",
    "                if indegree[v] == 0:\n",
    "                    Q.append(v) \n",
    "        return max(dp) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "\n",
    "        class Cubolid:\n",
    "            def __init__(self, arr):\n",
    "                arr.sort(reverse=True)\n",
    "                self.h = arr[0]\n",
    "                self.w = arr[1]\n",
    "                self.l = arr[2]\n",
    "\n",
    "            def __repr__(self):\n",
    "                return f\"h:{self.h}|w:{self.w}|l:{self.l}\"\n",
    "\n",
    "        cuboids = sorted(\n",
    "            [Cubolid(cur) for cur in cuboids],\n",
    "            key=lambda cur: (cur.h, cur.w, cur.l)\n",
    "        )\n",
    "\n",
    "        n = len(cuboids)\n",
    "        # print (cuboids)\n",
    "        rdp, dp = [0] * n, [0] * n\n",
    "        for k in range(n):\n",
    "            dp_max = rdp_max = 0\n",
    "            for i in range(k):\n",
    "                if cuboids[i].w <= cuboids[k].w and cuboids[i].l <= cuboids[k].l and cuboids[i].h <= cuboids[k].h:\n",
    "                    dp_max = max(dp_max, dp[i])\n",
    "                    rdp_max = max(rdp_max, rdp[i])\n",
    "\n",
    "                if cuboids[i].l <= cuboids[k].w and cuboids[i].w <= cuboids[k].l:\n",
    "                    dp_max = max(dp_max, rdp[i])\n",
    "                    rdp_max = max(rdp_max, dp[i])\n",
    "\n",
    "            dp[k], rdp[k] = dp_max + cuboids[k].h, rdp_max + cuboids[k].h\n",
    "\n",
    "        # print (dp, rdp)\n",
    "\n",
    "        return max(max(dp), max(rdp))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "\n",
    "        class Cubolid:\n",
    "            def __init__(self, arr):\n",
    "                arr.sort(reverse=True)\n",
    "                self.h = arr[0]\n",
    "                self.w = arr[1]\n",
    "                self.l = arr[2]\n",
    "\n",
    "            def __repr__(self):\n",
    "                return f\"h:{self.h}|w:{self.w}|l:{self.l}\"\n",
    "\n",
    "        cuboids = sorted(\n",
    "            [Cubolid(cur) for cur in cuboids],\n",
    "            key=lambda cur: (cur.h, cur.w, cur.l)\n",
    "        )\n",
    "\n",
    "        n = len(cuboids)\n",
    "        # print (cuboids)\n",
    "        dp = [0] * n\n",
    "        for k in range(n):\n",
    "            dp_max = rdp_max = 0\n",
    "            for i in range(k):\n",
    "                if cuboids[i].w <= cuboids[k].w and cuboids[i].l <= cuboids[k].l and cuboids[i].h <= cuboids[k].h:\n",
    "                    dp_max = max(dp_max, dp[i])\n",
    "\n",
    "            dp[k] = dp_max + cuboids[k].h\n",
    "\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.max_tree = [0] * (n + 1)\n",
    "    def update(self, idx, val):\n",
    "        while idx <= self.n:\n",
    "            self.max_tree[idx] = max(self.max_tree[idx], val)\n",
    "            idx += idx & (-idx)\n",
    "    def query(self, idx):\n",
    "        res = 0\n",
    "        while idx > 0:\n",
    "            res = max(res, self.max_tree[idx])\n",
    "            idx -= idx & (-idx)\n",
    "        return res\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        n=len(cuboids)\n",
    "        for i in range(n):\n",
    "            cuboids[i].sort()\n",
    "        cuboids.sort(key=lambda x:(x[0],x[1],x[2]))\n",
    "        f=[z for x,y,z in cuboids]\n",
    "        pos=list(range(n))\n",
    "        pos.sort(key=lambda x:(cuboids[x][1],cuboids[x][2]))\n",
    "        def cdq(l,r,pos):\n",
    "            if l==r:return \n",
    "            mid=(l+r)//2\n",
    "            cdq(l,mid,[i for i in pos if i<=mid])\n",
    "            bit=BIT(105)\n",
    "            for i in pos:\n",
    "                if i<=mid:\n",
    "                    bit.update(cuboids[i][2],f[i])\n",
    "                else:\n",
    "                    f[i]=max(f[i],cuboids[i][2]+bit.query(cuboids[i][2]))\n",
    "            cdq(mid+1,r,[i for i in pos if i>mid])\n",
    "        cdq(0,n-1,pos)\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        arr = [(float('inf'),float('inf'),float('inf'),-1)]\n",
    "        for i, (w, l, h) in enumerate(cuboids):\n",
    "            arr.append((w, l, h, i))\n",
    "            arr.append((w, h, l, i))\n",
    "            arr.append((l, w, h, i))\n",
    "            arr.append((l, h, w, i))\n",
    "            arr.append((h, w, l, i))\n",
    "            arr.append((h, l, w, i))\n",
    "        arr.sort(key=lambda x : (-x[0], -x[1], -x[2]))\n",
    "        m = len(arr) \n",
    "        dp = [0] * m\n",
    "        for i in range(1, m):\n",
    "            for j in range(i):\n",
    "                if arr[i][0] <= arr[j][0] and arr[i][1] <= arr[j][1] and arr[i][2] <= arr[j][2] and arr[i][3] != arr[j][3]:\n",
    "                    dp[i] = max(dp[i], dp[j]+arr[i][2]) \n",
    "        return max(dp) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "\n",
    "        n = len(cuboids)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, pre):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if pre == -1:\n",
    "                for j in range(i, n):\n",
    "                    w2, l2, h2 = cuboids[j]\n",
    "                    res = max(res, dfs(j+1, j) + h2)\n",
    "            \n",
    "            else:\n",
    "                w1, l1, h1 = cuboids[pre]\n",
    "                for j in range(i, n):\n",
    "                    w2, l2, h2 = cuboids[j]\n",
    "                    if w1 <= w2 and l1 <= l2 and h1 <= h2:\n",
    "                        res = max(res, dfs(j+1, j) + h2)\n",
    "            return res \n",
    "\n",
    "        return dfs(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        cuboids = sorted(map(sorted,cuboids))\n",
    "        cuboids.append([inf,inf,inf])\n",
    "        n = len(cuboids)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(c,pre):\n",
    "            if c < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            #满足\n",
    "            if all(cuboids[c][i]<=cuboids[pre][i] for i in range(3)):\n",
    "                ans = max(ans, cuboids[c][2] + dfs(c-1,c))\n",
    "            #不满足或者不选\n",
    "            ans = max(ans, dfs(c-1,pre))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(n-2,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        cuboids = sorted(map(sorted,cuboids))\n",
    "        cuboids.append([inf,inf,inf])\n",
    "        n = len(cuboids)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(c,pre):\n",
    "            if c < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            #满足\n",
    "            if all(cuboids[c][i]<=cuboids[pre][i] for i in range(3)):\n",
    "                ans = max(ans, cuboids[c][2] + dfs(c-1,c))\n",
    "            #不满足或者不选\n",
    "            ans = max(ans, dfs(c-1,pre))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(n-2,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        # cuboids = sorted(map(sorted,cuboids))\n",
    "        # cuboids.append([inf,inf,inf])\n",
    "\n",
    "        for c in cuboids:\n",
    "            c.sort()\n",
    "        cuboids.sort()\n",
    "        cuboids.append([inf,inf,inf])\n",
    "        n = len(cuboids)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(c,pre):\n",
    "            if c < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            #满足\n",
    "            if all(cuboids[c][i]<=cuboids[pre][i] for i in range(3)):\n",
    "                ans = max(ans, cuboids[c][2] + dfs(c-1,c))\n",
    "            #不满足或者不选\n",
    "            ans = max(ans, dfs(c-1,pre))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(n-2,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, cuboids: List[List[int]]) -> int:\n",
    "        cub = sorted(map(sorted,cuboids))\n",
    "        cub.append([inf,inf,inf])\n",
    "        n = len(cub)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(c,pre):\n",
    "            if c < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            #满足\n",
    "            if all(cub[c][i]<=cub[pre][i] for i in range(3)):\n",
    "                ans = max(ans, cub[c][2] + dfs(c-1,c))\n",
    "            #不满足或者不选\n",
    "            ans = max(ans, dfs(c-1,pre))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(n-2,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHeight(self, boxes: List[List[int]]) -> int:\n",
    "        n = len(boxes)\n",
    "        for i in range(n):\n",
    "            boxes[i].sort()\n",
    "        boxes.sort()\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            if i == n:return 0\n",
    "            ans = dfs(i+1,j)\n",
    "            if j == -1:\n",
    "                ans = max(ans,dfs(i+1,i) + boxes[i][-1])\n",
    "            else:\n",
    "                if all(boxes[i][k] >= boxes[j][k] for k in range(3)):\n",
    "                    ans = max(ans,dfs(i+1,i) + boxes[i][-1])\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,-1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
